/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/permutation-index
@Language: C++
@Datetime: 16-02-09 05:14
*/

class Solution {
public:
    /**
     * @param A an integer array
     * @return a long integer
     */
    long long permutationIndex(vector<int>& A) {
        // Write your code here
        set<int> s;
        long long sum=0,id=0,floor=1,n=1;
        for(int i=A.size()-1;i>=0;--i){
            s.insert(A[i]);
            id = 0;
            for(set<int>::iterator it=s.begin();it!=s.end();++it,++id)
                if (*it == A[i])
                    break;
            sum+=id*floor;
            floor*=n++;
        }
        return sum+1;
    }
};